// // https://leetcode.cn/problems/kth-largest-element-in-an-array/submissions/678552935/
//快速选择排序
// // class Solution {
// // public:
// //     int findKthLargest(vector<int>& nums, int k) {
// //         // 第k大的意思是从小到大排序完，从后开始数的第k个元素
// //         srand(time(NULL));
// //         return myqsort(nums, 0, nums.size() - 1, k);
// //     }
// //     int myqsort(vector<int>& nums, int l, int r, int k)
// //     {
// //         if (l >= r)
// //             return nums[l];
// //         int ret = getTime(nums, l, r);
// //         int i = l;
// //         int left = l - 1;
// //         int right = r + 1;
// //         while (i < right) {
// //             if (nums[i] < ret) {
// //                 left++;
// //                 swap(nums[left], nums[i]);
// //                 i++;
// //             } else if (nums[i] == ret) {
// //                 i++;
// //             } else {
// //                 right--;
// //                 swap(nums[right], nums[i]);
// //             }
// //         }
// //         int c = r - right + 1;
// //         int b = right - left - 1;
// //         if (c >= k) {
// //            return myqsort(nums, right, r, k);
// //         } else if (b + c >= k) {
// //             return ret;
// //         } else {
// //            return myqsort(nums, l, left, k - c - b);
// //         }
// //     }
// //     int getTime(vector<int>& nums, int l, int r) {
// //         int ret = rand();
// //         return nums[ret % (r - l + 1) + l];
// //     }
// // };


// //快排
// https://leetcode.cn/problems/sort-an-array/
// class Solution {
// public:
//     vector<int> sortArray(vector<int>& nums) {
//         srand(time(NULL));
//         int r = nums.size();
//         mysort(nums, 0, r - 1);
//         return nums;
//     }
//     void mysort(vector<int>& nums, int l, int r) {
//         if (l >= r)
//             return;
//         int key = getTime(nums,l,r);
        
//         int i = l;
//         int left = l - 1;
//         int right = r + 1;
//         while (i < right) 
//         {
//             if (nums[i] < key) 
//             {
//                 left++;
//                 swap(nums[left], nums[i]);
//                 i++;
//             }
//             else if(nums[i] == key)
//             {
//                 i++;
//             }
//             else
//             {
//                 right--;
//                 swap(nums[right],nums[i]);
//             }
//         }
//         //l -left left+1~i i+1~right-1 right~r 分为这四个部分
//         mysort(nums,l,left);
//         mysort(nums,right,r);
//     }
//     int getTime(vector<int>& nums, int l, int r) {
//         int ret = rand();
//         return nums[ret % (r - l + 1) + l];
//     }
// };
// https://leetcode.cn/problems/sort-colors/submissions/
// class Solution {
// public:
//     void sortColors(vector<int>& nums) {
//         //三指针 
//         //第一个指针 i 的作用是遍历数组
//         //第二个指针 left的作用是left左边的是小于1的
//         //第三个指针 right的作用是right的右边是大于一的
//         //这三个指针可以把这个数组进行划分0—left的区域表示小于1的
//         //left+1-i 表示等于1的 i-rigjt-1的区域表示还没有进行划分的区域 right到最后表述大于1的区域
//         int i = 0;
//         int left = -1;
//         int right =nums.size();
//         while( i < right)
//         {
//             if(nums[i] < 1)
//             {
//                 left++;
//                 swap(nums[left],nums[i]);
//                 i++;
//             }else if( nums[i] == 1)
//             {
//                 i++;
//             }else
//             {
//                 right--;
//                 swap(nums[right],nums[i]);
//                 //这是i不++，因为i位置的交换过来的值，是没有划分区域的值
//             }
//         }
//     }
// };



// class Solution {
// public:
//     int reversePairs(vector<int>& record) {
//         //先搞懂一个问题
//         //举一个例子 7 5 4 6
//         //以这个例子为例子，假设左半边为7 5 右半边为 4 6
//         //我们可以先求左半边的逆序对，然后再求右边的逆序对，（这一步之前，我们可以先把左边排序，然后再把右边排序，这样并不影响我们找下一步找逆序对）最后在求一个数在左边，一个数在右边的逆序对。然后他们三个值相加
//         //为什么要排序 我们排序完是这样的 5 7 4 6
//         我们第一次选左边的5，右边的4，我们知道5 4为一个逆序对，然后
//         5右边的，而且属于左半部分的一定大于4也就一定构成逆序对，所以这样就少比对了，时间复杂度就会降低了
//     }
// };

//https://leetcode.cn/problems/shu-zu-zhong-de-ni-xu-dui-lcof/submissions/679077627/
// class Solution {
// public:
//     int reversePairs(vector<int>& record) {
//         if (record.empty())
//             return {};
//         return mergeSort(record, 0, record.size() - 1);;
//     }
//     int mergeSort(vector<int>& nums, int l, int r) {
//         if (l >= r)
//             return 0;
//         int ret = 0; int mid = (l + r) / 2;
//         // 递归划分
//         ret += mergeSort(nums, l, mid);
//         ret += mergeSort(nums, mid + 1, r);

//         // 合并两个有序数组
//         // 创建临时数组
//         vector<int> temp(r - l + 1);
//         int left = l;
//         int right = mid + 1;
//         int i = 0;

//         // 合并两个有序部分
//         while (left <= mid && right <= r) {
//             if (nums[left] <= nums[right]) {
//                 temp[i++] = nums[left++];
//             } else {
//                 ret += mid - left + 1;
//                 temp[i++] = nums[right++];
//             }
//         }

//         // 复制剩余元素
//         while (left <= mid) {
//             temp[i++] = nums[left++];
//         }
//         while (right <= r) {   
//             temp[i++] = nums[right++];
//         }

//         // 将临时数组复制回原数组
//         for (int j = 0; j < temp.size(); j++) {
//             nums[l + j] = temp[j];
//         }
//         return ret;
//     }
// };



// https://leetcode.cn/problems/count-of-smaller-numbers-after-self/submissions/

// class Solution {
// public:
//     vector<int> sum;
//     vector<int> countSmaller(vector<int>& nums) {
//         //这是求的是当前元素后面有多少个比我小，所以这里要用归并排序的降序
//         // 先进行归并排序
//         vector<int> nums2(nums.size());
//         sum.resize(nums.size());
//         for(int i = 0 ; i <nums.size() ;i++)
//         {
//             nums2[i]=i;
//         }
//         mysort(nums,0 ,nums.size()-1 ,nums2);
//         return sum;
//     }
//     void mysort(vector<int>& nums,int left ,int right,vector<int>& nums2)
//     {
//         if (left >= right) return ;
//         int mid = (left+right)/2;
//         mysort(nums,left,mid,nums2);
//         mysort(nums,mid+1,right,nums2);
//         int result = 0;
//         //在这一步要进行排序,我们要进行的是降序
//         int cur1 = left ;
//         int cur2 = mid+1 ;
//         vector<int> temp(right -left+ 1);
//         vector<int> temp2(right -left+ 1);
        
//         int ret = 0;
//         while (cur1 <= mid && cur2 <= right)
//         {
//             if(nums[cur1] <= nums[cur2])
//             {
//                 temp[ret] = nums[cur2];
//                 //在这里应该把他的位置的下标移动到里面
//                 temp2[ret] = nums2[cur2];
//                 ret++;cur2++;
//             }
//             else
//             {
//                 //因为我们nums和nums2是绑定了nums2保存了nums里面元素的下标
//                 //所以我们知道nums2[cur1]就一定指向原始的下标
//                 sum[nums2[cur1]] +=right -cur2 +1;
//                 temp[ret] = nums[cur1];
//                 temp2[ret] =nums2[cur1];
//                 ret++;cur1++;
//             }
//         }
//         // 复制剩余元素
//         while (cur1 <= mid) {
//             temp[ret] = nums[cur1];
//             temp2[ret] = nums2[cur1];
//             ret++;cur1++;
//         }
//         while (cur2 <= right) {   
//             temp[ret] = nums[cur2];
//             temp2[ret] =nums2[cur2];
//             ret++;cur2++;
//         }

//         //然后接下来我们需要复制代码到我们的数组
//         for(int i = 0 ;i < right -left +1 ;i++)
//         {
//             nums[left+i] =temp[i];
//             nums2[left+i] =temp2[i];
//         }



//     }
// };